package com.love.labuladong.str;

/**
 * @Author : zh
 * @Description : Sunday 算法
 *
 *
 *
 *
 * @Date : 2024-08-27 09:21
 */
public class Sunday {


    public static void main(String[] args) {
        String s1 = "abc";
        String s2 = "c";

        System.out.println(search(s1,s2));

    }


    public static int search(String haystack,String needle){
        if(needle.length() == 0){
            return 0;
        }

        char[] s = haystack.toCharArray();
        char[] p = needle.toCharArray();

        int slen = s.length;
        int plen = p.length;

        int i = 0;  // 主串位置指针
        int j = 0;  // 模式串位置指针
        int m = plen; //每次重新匹配，模式串尾部对应主串位置的下一位
        int k = 0; // 失配时模式串回溯位置指针

        while (i < slen && j < plen){
            // 如果失配
            if(s[i] != p[j]){
                // 如果m超出主串长度，表示模式串已经无法匹配
                if(m >= slen){
                    return -1;
                }
                // 遍历模式串，查看模式串中是否包含m位置的字符
                for (k = plen - 1; k >= 0 ; k--) {
                    if(p[k] == s[m]){
                        break;
                    }
                }
                // 确定包含字符的位置，即确定模式串移动位置，重新开始匹配
                i = m - k;
                j = 0;
                m = i + plen;
            }else {
                // 未匹配完成则继续匹配
                i++;
                j++;
            }
        }

        // 如果 j 已经遍历一次模式串，表示模式串匹配完成
        return j == plen ? i-j : -1;
    }

}
